home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Regexp / Regexp.C < prev    next >
C/C++ Source or Header  |  1992-05-20  |  33KB  |  1,201 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. //
  13. // Created: MNF 06/13/89 -- Initial Design and Implementation
  14. // Updated: MBN 09/08/89 -- Added conditional exception handling
  15. // Updated: MBN 12/15/89 -- Sprinkled "const" qualifiers all over the place!
  16. // Updated: MJF 03/12/90 -- Added group names to RAISE
  17. // Updated: DLS 03/22/91 -- New lite version
  18. //
  19. // This file contains the implementation for the member functions of the CoolRegexp
  20. // class.  The  CoolRegexp class is  defined  in the  CoolRegexp.h   header file.  More
  21. // documentation is also available  in that file.   A  significant part of this
  22. // file is derived directly from other work done on regular expressions.   That
  23. // part is so marked.
  24. //
  25.  
  26. #ifndef REGEXPH                    // If CoolRegexp class not define
  27. #include <cool/Regexp.h>            // Include class specification 
  28. #endif
  29.  
  30. #if defined(DOS)
  31. extern "C" {
  32. #include <stdlib.h>                // For abort()
  33. }
  34. #else
  35. #include <stdlib.h>                
  36. #endif
  37.  
  38.  
  39. // ~CoolRegexp -- Destructor for CoolRegexp class (not inline because it's virtual)
  40. // Input:     None
  41. // Output:    None
  42.  
  43. CoolRegexp::~CoolRegexp () {
  44.   delete [] this->program;
  45. }
  46.  
  47.  
  48. // CoolRegexp -- Copy constructor duplicates its values and state
  49. // Input:    Reference to a Regular Expression 
  50. // Output:   None
  51.  
  52. CoolRegexp::CoolRegexp (const CoolRegexp& rxp) {
  53.   int ind; 
  54.   this->progsize = rxp.progsize;        // Copy regular expression size
  55.   this->program = new char[this->progsize];    // Allocate storage
  56.   for(ind=this->progsize; ind-- != 0;)        // Copy regular expresion
  57.     this->program[ind] = rxp.program[ind];
  58.   this->startp[0] = rxp.startp[0];        // Copy pointers into last
  59.   this->endp[0] = rxp.endp[0];            // Successful "find" operation
  60.   this->regmust = rxp.regmust;            // Copy field
  61.   if (rxp.regmust != NULL) {
  62.     char* dum = rxp.program;
  63.     ind = 0;
  64.     while (dum != rxp.regmust) {
  65.       ++dum;
  66.       ++ind;
  67.     }
  68.     this->regmust = this->program + ind;
  69.   }
  70.   this->regstart = rxp.regstart;        // Copy starting index
  71.   this->reganch = rxp.reganch;            // Copy remaining private data
  72.   this->regmlen = rxp.regmlen;            // Copy remaining private data
  73. }
  74.      
  75.  
  76. // operator== -- Overload the equality operator for the CoolRegexp class. Two CoolRegexp
  77. //               are == if their programs are the same.
  78. // Input:        A reference to a regular expression.
  79. // Output:       Boolean TRUE/FALSE
  80.  
  81. Boolean CoolRegexp::operator== (const CoolRegexp& rxp) const {
  82.   int ind = this->progsize;            // Get regular expression size
  83.   if (ind != rxp.progsize)            // If different size regexp
  84.     return FALSE;                // Return failure
  85.   while(ind-- != 0)                // Else while still characters
  86.     if(this->program[ind] != rxp.program[ind])    // If regexp are different    
  87.       return FALSE;                // Return failure             
  88.   return TRUE;                    // Else same, return success  
  89. }
  90.  
  91.  
  92. // deep_equal -- Two CoolRegexp objects that are deep_equal are both == and have
  93. //               the same startp[0] and endp[0] pointers. This means that they
  94. //               have the same compiled regular expression and they last
  95. //               matched on the same identical string.
  96. // Input:        A reference to a CoolRegexp object.
  97. // Output:       Boolean TRUE/FALSE
  98.  
  99. Boolean CoolRegexp::deep_equal (const CoolRegexp& rxp) const {
  100.   int ind = this->progsize;            // Get regular expression size
  101.   if (ind != rxp.progsize)            // If different size regexp
  102.     return FALSE;                // Return failure
  103.   while(ind-- != 0)                // Else while still characters
  104.     if(this->program[ind] != rxp.program[ind])    // If regexp are different    
  105.       return FALSE;                // Return failure             
  106.   return (this->startp[0] == rxp.startp[0] &&     // Else if same start/end ptrs,
  107.       this->endp[0] == rxp.endp[0]);    // Return TRUE
  108. }   
  109.  
  110. // The remaining code in this file is derived from the  regular expression code
  111. // whose  copyright statement appears  below.  It has been  changed to work
  112. // with the class concepts of C++ and COOL.
  113.  
  114. /*
  115.  * compile and find 
  116.  *
  117.  *    Copyright (c) 1986 by University of Toronto.
  118.  *    Written by Henry Spencer.  Not derived from licensed software.
  119.  *
  120.  *    Permission is granted to anyone to use this software for any
  121.  *    purpose on any computer system, and to redistribute it freely,
  122.  *    subject to the following restrictions:
  123.  *
  124.  *    1. The author is not responsible for the consequences of use of
  125.  *        this software, no matter how awful, even if they arise
  126.  *        from defects in it.
  127.  *
  128.  *    2. The origin of this software must not be misrepresented, either
  129.  *        by explicit claim or by omission.
  130.  *
  131.  *    3. Altered versions must be plainly marked as such, and must not
  132.  *        be misrepresented as being the original software.
  133.  *
  134.  * Beware that some of this code is subtly aware of the way operator
  135.  * precedence is structured in regular expressions.  Serious changes in
  136.  * regular-expression syntax might require a total rethink.
  137.  */
  138.  
  139. /*
  140.  * The "internal use only" fields in regexp.h are present to pass info from
  141.  * compile to execute that permits the execute phase to run lots faster on
  142.  * simple cases.  They are:
  143.  *
  144.  * regstart    char that must begin a match; '\0' if none obvious
  145.  * reganch    is the match anchored (at beginning-of-line only)?
  146.  * regmust    string (pointer into program) that match must include, or NULL
  147.  * regmlen    length of regmust string
  148.  *
  149.  * Regstart and reganch permit very fast decisions on suitable starting points
  150.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  151.  * of lines that cannot possibly match.  The regmust tests are costly enough
  152.  * that compile() supplies a regmust only if the r.e. contains something
  153.  * potentially expensive (at present, the only such thing detected is * or +
  154.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  155.  * supplied because the test in find() needs it and compile() is computing
  156.  * it anyway.
  157.  */
  158.  
  159. /*
  160.  * Structure for regexp "program".  This is essentially a linear encoding
  161.  * of a nondeterministic finite-state machine (aka syntax charts or
  162.  * "railroad normal form" in parsing technology).  Each node is an opcode
  163.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  164.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  165.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  166.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  167.  * opposed to a collection of them) is never concatenated with anything
  168.  * because of operator precedence.)  The operand of some types of node is
  169.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  170.  * particular, the operand of a BRANCH node is the first node of the branch.
  171.  * (NB this is *not* a tree structure:  the tail of the branch connects
  172.  * to the thing following the set of BRANCHes.)  The opcodes are:
  173.  */
  174.  
  175. // definition    number    opnd?    meaning
  176. #define    END    0        // no    End of program.
  177. #define    BOL    1        // no    Match "" at beginning of line.
  178. #define    EOL    2        // no    Match "" at end of line.
  179. #define    ANY    3        // no    Match any one character.
  180. #define    ANYOF    4        // str    Match any character in this string.
  181. #define    ANYBUT    5        // str    Match any character not in this
  182.                 // string.
  183. #define    BRANCH    6        // node    Match this alternative, or the
  184.                 // next...
  185. #define    BACK    7        // no    Match "", "next" ptr points backward.
  186. #define    EXACTLY    8        // str    Match this string.
  187. #define    NOTHING    9        // no    Match empty string.
  188. #define    STAR    10        // node    Match this (simple) thing 0 or more
  189.                 // times.
  190. #define    PLUS    11        // node    Match this (simple) thing 1 or more
  191.                 // times.
  192. #define    OPEN    20        // no    Mark this point in input as start of
  193.                 // #n.
  194. // OPEN+1 is number 1, etc.
  195. #define    CLOSE    30        // no    Analogous to OPEN.
  196.  
  197. /*
  198.  * Opcode notes:
  199.  *
  200.  * BRANCH    The set of branches constituting a single choice are hooked
  201.  *        together with their "next" pointers, since precedence prevents
  202.  *        anything being concatenated to any individual branch.  The
  203.  *        "next" pointer of the last BRANCH in a choice points to the
  204.  *        thing following the whole choice.  This is also where the
  205.  *        final "next" pointer of each individual branch points; each
  206.  *        branch starts with the operand node of a BRANCH node.
  207.  *
  208.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  209.  *        exists to make loop structures possible.
  210.  *
  211.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  212.  *        BRANCH structures using BACK.  Simple cases (one character
  213.  *        per match) are implemented with STAR and PLUS for speed
  214.  *        and to minimize recursive plunges.
  215.  *
  216.  * OPEN,CLOSE    ...are numbered at compile time.
  217.  */
  218.  
  219. /*
  220.  * A node is one char of opcode followed by two chars of "next" pointer.
  221.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  222.  * value is a positive offset from the opcode of the node containing it.
  223.  * An operand, if any, simply follows the node.  (Note that much of the
  224.  * code generation knows about this implicit relationship.)
  225.  *
  226.  * Using two bytes for the "next" pointer is vast overkill for most things,
  227.  * but allows patterns to get big without disasters.
  228.  */
  229.  
  230. #define    OP(p)        (*(p))
  231. #define    NEXT(p)        (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  232. #define    OPERAND(p)    ((p) + 3)
  233.  
  234.  
  235. /*
  236.  * Utility definitions.
  237.  */
  238. #ifndef CHARBITS
  239. #define    UCHARAT(p)    ((int)*(const unsigned char*)(p))
  240. #else
  241. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  242. #endif
  243.  
  244. #define    FAIL(m)    { regerror(m); return(NULL); }
  245. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  246. #define    META    "^$.[()|?+*\\"
  247.  
  248.  
  249. /*
  250.  * Flags to be passed up and down.
  251.  */
  252. #define    HASWIDTH    01    // Known never to match null string.
  253. #define    SIMPLE        02    // Simple enough to be STAR/PLUS operand.
  254. #define    SPSTART        04    // Starts with * or +.
  255. #define    WORST        0    // Worst case.
  256.  
  257.  
  258.  
  259. /////////////////////////////////////////////////////////////////////////
  260. //
  261. //  COMPILE AND ASSOCIATED FUNCTIONS
  262. //
  263. /////////////////////////////////////////////////////////////////////////
  264.  
  265.  
  266. /*
  267.  * Global work variables for compile().
  268.  */
  269. static const char* regparse;    // Input-scan pointer.
  270. static       int   regnpar;    // () count.
  271. static       char  regdummy;
  272. static       char* regcode;    // Code-emit pointer; ®dummy = don't.
  273. static       long  regsize;    // Code size.
  274.  
  275. /*
  276.  * Forward declarations for compile()'s friends.
  277.  */
  278. #ifndef STATIC
  279. #define    STATIC    static
  280. #endif
  281. STATIC       char* reg (int, int*);
  282. STATIC       char* regbranch (int*);
  283. STATIC       char* regpiece (int*);
  284. STATIC       char* regatom (int*);
  285. STATIC       char* regnode (char);
  286. STATIC const char* regnext (register const char*);
  287. STATIC       char* regnext (register char*);
  288. STATIC void        regc (char);
  289. STATIC void        reginsert (char, char*);
  290. STATIC void        regtail (char*, const char*);
  291. STATIC void        regoptail (char*, const char*);
  292.  
  293. #ifdef STRCSPN
  294. STATIC int strcspn ();
  295. #endif
  296.  
  297.  
  298. /*
  299.  - compile - compile a regular expression into internal code
  300.  *
  301.  * We can't allocate space until we know how big the compiled form will be,
  302.  * but we can't compile it (and thus know how big it is) until we've got a
  303.  * place to put the code.  So we cheat:  we compile it twice, once with code
  304.  * generation turned off and size counting turned on, and once "for real".
  305.  * This also means that we don't allocate space until we are sure that the
  306.  * thing really will compile successfully, and we never have to move the
  307.  * code and thus invalidate pointers into it.  (Note that it has to be in
  308.  * one piece because free() must be able to free it all.)
  309.  *
  310.  * Beware that the optimization-preparation code in here knows about some
  311.  * of the structure of the compiled regexp.
  312.  */
  313. void CoolRegexp::compile (const char* exp) {
  314.     register const char* scan;
  315.     register const char* longest;
  316.     register int         len;
  317.              int         flags;
  318.  
  319.     if (exp == NULL) {
  320.       //RAISE (Error, SYM(CoolRegexp), SYM(No_Expr),
  321.       printf ("CoolRegexp::compile(): No expression supplied.\n");
  322.       abort ();
  323.     }
  324.  
  325.     // First pass: determine size, legality.
  326.     regparse = exp;
  327.     regnpar = 1;
  328.     regsize = 0L;
  329.     regcode = ®dummy;
  330.     regc(MAGIC);
  331.     reg(0, &flags);
  332.     this->startp[0] = this->endp[0] = this->searchstring = NULL;
  333.  
  334.     // Small enough for pointer-storage convention? 
  335.     if (regsize >= 32767L) {    // Probably could be 65535L. 
  336.       //RAISE (Error, SYM(CoolRegexp), SYM(Expr_Too_Big),
  337.       printf ("CoolRegexp::compile(): Expression too big.\n");
  338.       abort ();
  339.     }
  340.  
  341.     // Allocate space. 
  342.     if (this->program != NULL) delete [] this->program;  
  343.     this->program = new char[regsize];
  344.     this->progsize = (int) regsize;
  345.  
  346.     if (this->program == NULL) {
  347.       //RAISE (Error, SYM(CoolRegexp), SYM(Out_Of_Memory),
  348.       printf ("CoolRegexp::compile(): Out of memory.\n"); 
  349.       abort ();
  350.     }
  351.  
  352.     // Second pass: emit code.
  353.     regparse = exp;
  354.     regnpar = 1;
  355.     regcode = this->program;
  356.     regc(MAGIC);
  357.     reg(0, &flags);
  358.  
  359.     // Dig out information for optimizations.
  360.     this->regstart = '\0';        // Worst-case defaults.
  361.     this->reganch = 0;
  362.     this->regmust = NULL;
  363.     this->regmlen = 0;
  364.     scan = this->program + 1;    // First BRANCH.
  365.     if (OP(regnext(scan)) == END) {    // Only one top-level choice.
  366.     scan = OPERAND(scan);
  367.  
  368.     // Starting-point info.
  369.     if (OP(scan) == EXACTLY)
  370.         this->regstart = *OPERAND(scan);
  371.     else if (OP(scan) == BOL)
  372.         this->reganch++;
  373.  
  374.      //
  375.      // If there's something expensive in the r.e., find the longest
  376.      // literal string that must appear and make it the regmust.  Resolve
  377.      // ties in favor of later strings, since the regstart check works
  378.      // with the beginning of the r.e. and avoiding duplication
  379.      // strengthens checking.  Not a strong reason, but sufficient in the
  380.      // absence of others. 
  381.      //
  382.     if (flags & SPSTART) {
  383.         longest = NULL;
  384.         len = 0;
  385.         for (; scan != NULL; scan = regnext(scan))
  386.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  387.             longest = OPERAND(scan);
  388.             len = strlen(OPERAND(scan));
  389.         }
  390.         this->regmust = longest;
  391.         this->regmlen = len;
  392.     }
  393.     }
  394. }
  395.  
  396.  
  397. /*
  398.  - reg - regular expression, i.e. main body or parenthesized thing
  399.  *
  400.  * Caller must absorb opening parenthesis.
  401.  *
  402.  * Combining parenthesis handling with the base level of regular expression
  403.  * is a trifle forced, but the need to tie the tails of the branches to what
  404.  * follows makes it hard to avoid.
  405.  */
  406. static char* reg (int paren, int *flagp) {
  407.     register char* ret;
  408.     register char* br;
  409.     register char* ender;
  410.     register int   parno;
  411.              int   flags;
  412.  
  413.     *flagp = HASWIDTH;        // Tentatively.
  414.  
  415.     // Make an OPEN node, if parenthesized.
  416.     if (paren) {
  417.     if (regnpar >= NSUBEXP) {
  418.       //RAISE (Error, SYM(CoolRegexp), SYM(Too_Many_Parens),
  419.       printf ("CoolRegexp::compile(): Too many parentheses.\n");
  420.       abort ();
  421.         }
  422.     parno = regnpar;
  423.     regnpar++;
  424.     ret = regnode(OPEN + parno);
  425.     }
  426.     else
  427.     ret = NULL;
  428.  
  429.     // Pick up the branches, linking them together.
  430.     br = regbranch(&flags);
  431.     if (br == NULL)
  432.     return (NULL);
  433.     if (ret != NULL)
  434.     regtail(ret, br);    // OPEN -> first.
  435.     else
  436.     ret = br;
  437.     if (!(flags & HASWIDTH))
  438.     *flagp &= ~HASWIDTH;
  439.     *flagp |= flags & SPSTART;
  440.     while (*regparse == '|') {
  441.     regparse++;
  442.     br = regbranch(&flags);
  443.     if (br == NULL)
  444.         return (NULL);
  445.     regtail(ret, br);    // BRANCH -> BRANCH.
  446.     if (!(flags & HASWIDTH))
  447.         *flagp &= ~HASWIDTH;
  448.     *flagp |= flags & SPSTART;
  449.       }
  450.  
  451.     // Make a closing node, and hook it on the end.
  452.     ender = regnode((paren) ? CLOSE + parno : END);
  453.     regtail(ret, ender);
  454.  
  455.     // Hook the tails of the branches to the closing node.
  456.     for (br = ret; br != NULL; br = regnext(br))
  457.     regoptail(br, ender);
  458.  
  459.     // Check for proper termination.
  460.     if (paren && *regparse++ != ')') {
  461.         //RAISE (Error, SYM(CoolRegexp), SYM(Unmatched_Parens),
  462.         printf ("CoolRegexp::compile(): Unmatched parentheses.\n");
  463.     abort ();
  464.     }
  465.     else if (!paren && *regparse != '\0') {
  466.         if (*regparse == ')') {
  467.             //RAISE (Error, SYM(CoolRegexp), SYM(Unmatched_Parens),
  468.             printf ("CoolRegexp::compile(): Unmatched parentheses.\n");
  469.         abort ();
  470.     }
  471.     else {
  472.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  473.         printf ("CoolRegexp::compile(): Internal error.\n");
  474.         abort ();
  475.         }
  476.     // NOTREACHED
  477.     }
  478.     return (ret);
  479. }
  480.  
  481.  
  482. /*
  483.  - regbranch - one alternative of an | operator
  484.  *
  485.  * Implements the concatenation operator.
  486.  */
  487. static char* regbranch (int *flagp) {
  488.     register char* ret;
  489.     register char* chain;
  490.     register char* latest;
  491.     int                  flags;
  492.  
  493.     *flagp = WORST;        // Tentatively.
  494.  
  495.     ret = regnode(BRANCH);
  496.     chain = NULL;
  497.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  498.     latest = regpiece(&flags);
  499.     if (latest == NULL)
  500.         return (NULL);
  501.     *flagp |= flags & HASWIDTH;
  502.     if (chain == NULL)    // First piece.
  503.         *flagp |= flags & SPSTART;
  504.     else
  505.         regtail(chain, latest);
  506.     chain = latest;
  507.     }
  508.     if (chain == NULL)        // Loop ran zero times.
  509.     regnode(NOTHING);
  510.  
  511.     return (ret);
  512. }
  513.  
  514.  
  515. /*
  516.  - regpiece - something followed by possible [*+?]
  517.  *
  518.  * Note that the branching code sequences used for ? and the general cases
  519.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  520.  * both the endmarker for their branch list and the body of the last branch.
  521.  * It might seem that this node could be dispensed with entirely, but the
  522.  * endmarker role is not redundant.
  523.  */
  524. static char* regpiece (int *flagp) {
  525.     register char* ret;
  526.     register char  op;
  527.     register char* next;
  528.     int            flags;
  529.  
  530.     ret = regatom(&flags);
  531.     if (ret == NULL)
  532.     return (NULL);
  533.  
  534.     op = *regparse;
  535.     if (!ISMULT(op)) {
  536.     *flagp = flags;
  537.     return (ret);
  538.     }
  539.  
  540.     if (!(flags & HASWIDTH) && op != '?') {
  541.         //RAISE (Error, SYM(CoolRegexp), SYM(Empty_Operand),
  542.         printf ("CoolRegexp::compile() : *+ operand could be empty.\n");
  543.     abort ();
  544.     }
  545.     *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
  546.  
  547.     if (op == '*' && (flags & SIMPLE))
  548.     reginsert(STAR, ret);
  549.     else if (op == '*') {
  550.     // Emit x* as (x&|), where & means "self".
  551.     reginsert(BRANCH, ret);    // Either x
  552.     regoptail(ret, regnode(BACK));    // and loop
  553.     regoptail(ret, ret);    // back
  554.     regtail(ret, regnode(BRANCH));    // or
  555.     regtail(ret, regnode(NOTHING));    // null.
  556.     }
  557.     else if (op == '+' && (flags & SIMPLE))
  558.     reginsert(PLUS, ret);
  559.     else if (op == '+') {
  560.     // Emit x+ as x(&|), where & means "self".
  561.     next = regnode(BRANCH);    // Either
  562.     regtail(ret, next);
  563.     regtail(regnode(BACK), ret);    // loop back
  564.     regtail(next, regnode(BRANCH));    // or
  565.     regtail(ret, regnode(NOTHING));    // null.
  566.     }
  567.     else if (op == '?') {
  568.     // Emit x? as (x|)
  569.     reginsert(BRANCH, ret);    // Either x
  570.     regtail(ret, regnode(BRANCH));    // or
  571.     next = regnode(NOTHING);// null.
  572.     regtail(ret, next);
  573.     regoptail(ret, next);
  574.     }
  575.     regparse++;
  576.     if (ISMULT(*regparse)) {
  577.         //RAISE (Error, SYM(CoolRegexp), SYM(Nested_Operand),
  578.         printf ("CoolRegexp::compile(): Nested *?+.\n");
  579.     abort ();
  580.     }
  581.     return (ret);
  582. }
  583.  
  584.  
  585. /*
  586.  - regatom - the lowest level
  587.  *
  588.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  589.  * it can turn them into a single node, which is smaller to store and
  590.  * faster to run.  Backslashed characters are exceptions, each becoming a
  591.  * separate node; the code is simpler that way and it's not worth fixing.
  592.  */
  593. static char* regatom (int *flagp) {
  594.     register char* ret;
  595.              int   flags;
  596.  
  597.     *flagp = WORST;        // Tentatively.
  598.  
  599.     switch (*regparse++) {
  600.     case '^':
  601.         ret = regnode(BOL);
  602.         break;
  603.     case '$':
  604.         ret = regnode(EOL);
  605.         break;
  606.     case '.':
  607.         ret = regnode(ANY);
  608.         *flagp |= HASWIDTH | SIMPLE;
  609.         break;
  610.     case '[':{
  611.         register int    rxpclass;
  612.         register int    rxpclassend;
  613.  
  614.         if (*regparse == '^') {    // Complement of range.
  615.             ret = regnode(ANYBUT);
  616.             regparse++;
  617.         }
  618.         else
  619.             ret = regnode(ANYOF);
  620.         if (*regparse == ']' || *regparse == '-')
  621.             regc(*regparse++);
  622.         while (*regparse != '\0' && *regparse != ']') {
  623.             if (*regparse == '-') {
  624.             regparse++;
  625.             if (*regparse == ']' || *regparse == '\0')
  626.                 regc('-');
  627.             else {
  628.                 rxpclass = UCHARAT(regparse - 2) + 1;
  629.                 rxpclassend = UCHARAT(regparse);
  630.                 if (rxpclass > rxpclassend + 1) {
  631.                    //RAISE (Error, SYM(CoolRegexp), SYM(Invalid_Range),
  632.                    printf ("CoolRegexp::compile(): Invalid range in [].\n");
  633.                    abort ();
  634.                             }
  635.                 for (; rxpclass <= rxpclassend; rxpclass++)
  636.                 regc(rxpclass);
  637.                 regparse++;
  638.             }
  639.             }
  640.             else
  641.             regc(*regparse++);
  642.         }
  643.         regc('\0');
  644.         if (*regparse != ']') {
  645.                     //RAISE (Error, SYM(CoolRegexp), SYM(Unmatched_Bracket),
  646.                     printf ("CoolRegexp::compile(): Unmatched [].\n");
  647.             abort ();
  648.             }
  649.         regparse++;
  650.         *flagp |= HASWIDTH | SIMPLE;
  651.         }
  652.         break;
  653.     case '(':
  654.         ret = reg(1, &flags);
  655.         if (ret == NULL)
  656.         return (NULL);
  657.         *flagp |= flags & (HASWIDTH | SPSTART);
  658.         break;
  659.     case '\0':
  660.     case '|':
  661.     case ')':
  662.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  663.             printf ("CoolRegexp::compile(): Internal error.\n"); // Never here
  664.         abort ();
  665.     case '?':
  666.     case '+':
  667.     case '*':
  668.         //RAISE (Error, SYM(CoolRegexp), SYM(No_Operand),
  669.             printf ("CoolRegexp::compile(): ?+* follows nothing.\n");
  670.         abort ();
  671.     case '\\':
  672.         if (*regparse == '\0') {
  673.             //RAISE (Error, SYM(CoolRegexp), SYM(Trailing_Backslash),
  674.                 printf ("CoolRegexp::compile(): Trailing backslash.\n");
  675.         abort ();
  676.             }
  677.         ret = regnode(EXACTLY);
  678.         regc(*regparse++);
  679.         regc('\0');
  680.         *flagp |= HASWIDTH | SIMPLE;
  681.         break;
  682.     default:{
  683.         register int    len;
  684.         register char   ender;
  685.  
  686.         regparse--;
  687.         len = strcspn(regparse, META);
  688.         if (len <= 0) {
  689.             //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  690.                     printf ("CoolRegexp::compile(): Internal error.\n");
  691.             abort ();
  692.                 }
  693.         ender = *(regparse + len);
  694.         if (len > 1 && ISMULT(ender))
  695.             len--;    // Back off clear of ?+* operand.
  696.         *flagp |= HASWIDTH;
  697.         if (len == 1)
  698.             *flagp |= SIMPLE;
  699.         ret = regnode(EXACTLY);
  700.         while (len > 0) {
  701.             regc(*regparse++);
  702.             len--;
  703.         }
  704.         regc('\0');
  705.         }
  706.         break;
  707.     }
  708.     return (ret);
  709. }
  710.  
  711.  
  712. /*
  713.  - regnode - emit a node
  714.    Location.
  715.  */
  716. static char* regnode (char op) {
  717.     register char* ret;
  718.     register char* ptr;
  719.  
  720.     ret = regcode;
  721.     if (ret == ®dummy) {
  722.     regsize += 3;
  723.     return (ret);
  724.     }
  725.  
  726.     ptr = ret;
  727.     *ptr++ = op;
  728.     *ptr++ = '\0';        // Null "next" pointer.
  729.     *ptr++ = '\0';
  730.     regcode = ptr;
  731.  
  732.     return (ret);
  733. }
  734.  
  735.  
  736. /*
  737.  - regc - emit (if appropriate) a byte of code
  738.  */
  739. static void regc (char b) {
  740.     if (regcode != ®dummy)
  741.     *regcode++ = b;
  742.     else
  743.     regsize++;
  744. }
  745.  
  746.  
  747. /*
  748.  - reginsert - insert an operator in front of already-emitted operand
  749.  *
  750.  * Means relocating the operand.
  751.  */
  752. static void reginsert (char op, char* opnd) {
  753.     register char* src;
  754.     register char* dst;
  755.     register char* place;
  756.  
  757.     if (regcode == ®dummy) {
  758.     regsize += 3;
  759.     return;
  760.     }
  761.  
  762.     src = regcode;
  763.     regcode += 3;
  764.     dst = regcode;
  765.     while (src > opnd)
  766.     *--dst = *--src;
  767.  
  768.     place = opnd;        // Op node, where operand used to be.
  769.     *place++ = op;
  770.     *place++ = '\0';
  771.     *place++ = '\0';
  772. }
  773.  
  774.  
  775. /*
  776.  - regtail - set the next-pointer at the end of a node chain
  777.  */
  778. static void regtail (char* p, const char* val) {
  779.     register char* scan;
  780.     register char* temp;
  781.     register int   offset;
  782.  
  783.     if (p == ®dummy)
  784.     return;
  785.  
  786.     // Find last node.
  787.     scan = p;
  788.     for (;;) {
  789.     temp = regnext(scan);
  790.     if (temp == NULL)
  791.         break;
  792.     scan = temp;
  793.     }
  794.  
  795.     if (OP(scan) == BACK)
  796.     offset = (const char*)scan - val;
  797.     else
  798.     offset = val - scan;
  799.     *(scan + 1) = (offset >> 8) & 0377;
  800.     *(scan + 2) = offset & 0377;
  801. }
  802.  
  803.  
  804. /*
  805.  - regoptail - regtail on operand of first argument; nop if operandless
  806.  */
  807. static void regoptail (char* p, const char* val) {
  808.     // "Operandless" and "op != BRANCH" are synonymous in practice.
  809.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  810.     return;
  811.     regtail(OPERAND(p), val);
  812. }
  813.  
  814.  
  815.  
  816. ////////////////////////////////////////////////////////////////////////
  817. // 
  818. //  find and friends
  819. // 
  820. ////////////////////////////////////////////////////////////////////////
  821.  
  822.  
  823. /*
  824.  * Global work variables for find().
  825.  */
  826. static const char*  reginput;    // String-input pointer.
  827. static const char*  regbol;    // Beginning of input, for ^ check.
  828. static const char* *regstartp;    // Pointer to startp array.
  829. static const char* *regendp;    // Ditto for endp.
  830.  
  831. /*
  832.  * Forwards.
  833.  */
  834. STATIC int regtry (const char*, const char*[NSUBEXP],
  835.            const char*[NSUBEXP], const char*);
  836. STATIC int regmatch (const char*);
  837. STATIC int regrepeat (const char*);
  838.  
  839. #ifdef DEBUG
  840. int          regnarrate = 0;
  841. void         regdump ();
  842. STATIC char* regprop ();
  843. #endif
  844.  
  845.  
  846. /*
  847.  - find - match a regexpr against a string
  848.  */
  849. Boolean CoolRegexp::find (const char* string) {
  850.     register const char* s;
  851.     
  852.     this->searchstring = string;
  853.  
  854.      // Check validity of program.
  855.     if (UCHARAT(this->program) != MAGIC) {
  856.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  857.         printf ("CoolRegexp::find(): Compiled regular expression corrupted.\n");
  858.     abort ();
  859.     }
  860.     
  861.     // If there is a "must appear" string, look for it.
  862.     if (this->regmust != NULL) {
  863.     s = string;
  864.     while ((s = strchr(s, this->regmust[0])) != NULL) {
  865.         if (strncmp(s, this->regmust, this->regmlen) == 0)
  866.         break;        // Found it.
  867.         s++;
  868.     }
  869.     if (s == NULL)        // Not present.
  870.         return (0);
  871.     }
  872.      
  873.     // Mark beginning of line for ^ .
  874.     regbol = string;
  875.  
  876.     // Simplest case:  anchored match need be tried only once.
  877.     if (this->reganch)
  878.     return (regtry(string, this->startp, this->endp, this->program));
  879.     
  880.     // Messy cases:  unanchored match.
  881.     s = string;
  882.     if (this->regstart != '\0')
  883.     // We know what char it must start with.
  884.     while ((s = strchr(s, this->regstart)) != NULL) {
  885.         if (regtry(s, this->startp, this->endp, this->program))
  886.         return (1);
  887.         s++;
  888.       
  889.     }
  890.     else
  891.     // We don't -- general case.
  892.     do {
  893.         if (regtry(s, this->startp, this->endp, this->program))
  894.         return (1);
  895.     } while (*s++ != '\0');
  896.     
  897.     // Failure.
  898.     return (0);
  899. }
  900.  
  901.  
  902. /*
  903.  - regtry - try match at specific point
  904.    0 failure, 1 success
  905.  */
  906. static int regtry (const char* string, const char* *start,
  907.            const char* *end, const char* prog) {
  908.     register       int    i;
  909.     register const char* *sp1;
  910.     register const char* *ep;
  911.  
  912.     reginput = string;
  913.     regstartp = start;
  914.     regendp = end;
  915.  
  916.     sp1 = start;
  917.     ep = end;
  918.     for (i = NSUBEXP; i > 0; i--) {
  919.     *sp1++ = NULL;
  920.     *ep++ = NULL;
  921.     }
  922.     if (regmatch(prog + 1)) {
  923.     start[0] = string;
  924.     end[0] = reginput;
  925.     return (1);
  926.     }
  927.     else
  928.     return (0);
  929. }
  930.  
  931.  
  932. /*
  933.  - regmatch - main matching routine
  934.  *
  935.  * Conceptually the strategy is simple:  check to see whether the current
  936.  * node matches, call self recursively to see whether the rest matches,
  937.  * and then act accordingly.  In practice we make some effort to avoid
  938.  * recursion, in particular by going through "ordinary" nodes (that don't
  939.  * need to know whether the rest of the match failed) by a loop instead of
  940.  * by recursion.
  941.  * 0 failure, 1 success
  942.  */
  943. static int regmatch (const char* prog) {
  944.     register const char* scan;    // Current node.
  945.              const char* next;    // Next node.
  946.  
  947.     scan = prog;
  948.  
  949.     while (scan != NULL) {
  950.  
  951.     next = regnext(scan);
  952.  
  953.     switch (OP(scan)) {
  954.         case BOL:
  955.         if (reginput != regbol)
  956.             return (0);
  957.         break;
  958.         case EOL:
  959.         if (*reginput != '\0')
  960.             return (0);
  961.         break;
  962.         case ANY:
  963.         if (*reginput == '\0')
  964.             return (0);
  965.         reginput++;
  966.         break;
  967.         case EXACTLY:{
  968.             register int         len;
  969.             register const char* opnd;
  970.  
  971.             opnd = OPERAND(scan);
  972.             // Inline the first character, for speed.
  973.             if (*opnd != *reginput)
  974.             return (0);
  975.             len = strlen(opnd);
  976.             if (len > 1 && strncmp(opnd, reginput, len) != 0)
  977.             return (0);
  978.             reginput += len;
  979.         }
  980.         break;
  981.         case ANYOF:
  982.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  983.             return (0);
  984.         reginput++;
  985.         break;
  986.         case ANYBUT:
  987.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  988.             return (0);
  989.         reginput++;
  990.         break;
  991.         case NOTHING:
  992.         break;
  993.         case BACK:
  994.         break;
  995.         case OPEN + 1:
  996.         case OPEN + 2:
  997.         case OPEN + 3:
  998.         case OPEN + 4:
  999.         case OPEN + 5:
  1000.         case OPEN + 6:
  1001.         case OPEN + 7:
  1002.         case OPEN + 8:
  1003.         case OPEN + 9:{
  1004.             register       int    no;
  1005.             register const char* save;
  1006.  
  1007.             no = OP(scan) - OPEN;
  1008.             save = reginput;
  1009.  
  1010.             if (regmatch(next)) {
  1011.  
  1012.             //
  1013.             // Don't set startp if some later invocation of the
  1014.             // same parentheses already has. 
  1015.             //
  1016.             if (regstartp[no] == NULL)
  1017.                 regstartp[no] = save;
  1018.             return (1);
  1019.             }
  1020.             else
  1021.             return (0);
  1022.         }
  1023.         break;
  1024.         case CLOSE + 1:
  1025.         case CLOSE + 2:
  1026.         case CLOSE + 3:
  1027.         case CLOSE + 4:
  1028.         case CLOSE + 5:
  1029.         case CLOSE + 6:
  1030.         case CLOSE + 7:
  1031.         case CLOSE + 8:
  1032.         case CLOSE + 9:{
  1033.             register       int    no;
  1034.             register const char* save;
  1035.  
  1036.             no = OP(scan) - CLOSE;
  1037.             save = reginput;
  1038.  
  1039.             if (regmatch(next)) {
  1040.  
  1041.             //
  1042.             // Don't set endp if some later invocation of the
  1043.             // same parentheses already has. 
  1044.             //
  1045.             if (regendp[no] == NULL)
  1046.                 regendp[no] = save;
  1047.             return (1);
  1048.             }
  1049.             else
  1050.             return (0);
  1051.         }
  1052.         break;
  1053.         case BRANCH:{
  1054.           
  1055.           register const char* save;
  1056.  
  1057.             if (OP(next) != BRANCH)    // No choice.
  1058.             next = OPERAND(scan);    // Avoid recursion.
  1059.             else {
  1060.             do {
  1061.                 save = reginput;
  1062.                 if (regmatch(OPERAND(scan)))
  1063.                 return (1);
  1064.                 reginput = save;
  1065.                 scan = regnext(scan);
  1066.             } while (scan != NULL && OP(scan) == BRANCH);
  1067.             return (0);
  1068.             // NOTREACHED
  1069.             }
  1070.         }
  1071.         break;
  1072.         case STAR:
  1073.         case PLUS:{
  1074.           register char   nextch;
  1075.             register int        no;
  1076.             register const char* save;
  1077.             register int        min_no;
  1078.  
  1079.             //
  1080.             // Lookahead to avoid useless match attempts when we know
  1081.             // what character comes next. 
  1082.             //
  1083.             nextch = '\0';
  1084.             if (OP(next) == EXACTLY)
  1085.             nextch = *OPERAND(next);
  1086.             min_no = (OP(scan) == STAR) ? 0 : 1;
  1087.             save = reginput;
  1088.             no = regrepeat(OPERAND(scan));
  1089.             while (no >= min_no) {
  1090.             // If it could work, try it.
  1091.             if (nextch == '\0' || *reginput == nextch)
  1092.                 if (regmatch(next))
  1093.                 return (1);
  1094.             // Couldn't or didn't -- back up.
  1095.             no--;
  1096.             reginput = save + no;
  1097.             }
  1098.             return (0);
  1099.         }
  1100.         break;
  1101.         case END:
  1102.          return (1);    // Success!
  1103.  
  1104.         default:
  1105.             //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  1106.                 printf ("CoolRegexp::find(): Internal error -- memory corrupted.\n");
  1107.         abort ();
  1108.     }
  1109.     scan = next;
  1110.     }
  1111.  
  1112.     // 
  1113.     //  We get here only if there's trouble -- normally "case END" is the
  1114.     //  terminating point. 
  1115.     // 
  1116.     //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  1117.     printf ("CoolRegexp::find(): Internal error -- corrupted pointers.\n");
  1118.     abort ();
  1119.     return (0);
  1120. }
  1121.  
  1122.  
  1123. /*
  1124.  - regrepeat - repeatedly match something simple, report how many
  1125.  */
  1126. static int regrepeat (const char* p) {
  1127.     register       int   count = 0;
  1128.     register const char* scan;
  1129.     register const char* opnd;
  1130.  
  1131.     scan = reginput;
  1132.     opnd = OPERAND(p);
  1133.     switch (OP(p)) {
  1134.     case ANY:
  1135.         count = strlen(scan);
  1136.         scan += count;
  1137.         break;
  1138.     case EXACTLY:
  1139.         while (*opnd == *scan) {
  1140.         count++;
  1141.         scan++;
  1142.         }
  1143.         break;
  1144.     case ANYOF:
  1145.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1146.         count++;
  1147.         scan++;
  1148.         }
  1149.         break;
  1150.     case ANYBUT:
  1151.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1152.         count++;
  1153.         scan++;
  1154.         }
  1155.         break;
  1156.     default:        // Oh dear.  Called inappropriately.
  1157.         //RAISE (Error, SYM(CoolRegexp), SYM(Internal_Error),
  1158.         printf ("CoolRegexp::find(): Internal error.\n");
  1159.         abort ();
  1160.     }
  1161.     reginput = scan;
  1162.     return (count);
  1163. }
  1164.  
  1165.  
  1166. /*
  1167.  - regnext - dig the "next" pointer out of a node
  1168.  */
  1169. static const char* regnext (register const char* p) {
  1170.     register int offset;
  1171.  
  1172.     if (p == ®dummy)
  1173.     return (NULL);
  1174.  
  1175.     offset = NEXT(p);
  1176.     if (offset == 0)
  1177.     return (NULL);
  1178.  
  1179.     if (OP(p) == BACK)
  1180.     return (p - offset);
  1181.     else
  1182.     return (p + offset);
  1183. }
  1184.  
  1185.  
  1186. static char* regnext (register char* p) {
  1187.     register int offset;
  1188.  
  1189.     if (p == ®dummy)
  1190.     return (NULL);
  1191.  
  1192.     offset = NEXT(p);
  1193.     if (offset == 0)
  1194.     return (NULL);
  1195.  
  1196.     if (OP(p) == BACK)
  1197.     return (p - offset);
  1198.     else
  1199.     return (p + offset);
  1200. }
  1201.